#include <catch2/catch.hpp>

#include <array>
#include "solution.hpp"

using namespace solution_045;

TEST_CASE("045_jump_game_ii", "[045]")
{
    SECTION("example 1") {
        auto nums = std::vector{2,3,1,1,4};
        CHECK(Solution().jump(nums) == 2);
    }

    SECTION("example 2") {
        auto nums = std::vector{2,3,0,1,4};
        CHECK(Solution().jump(nums) == 2);
    }

    SECTION("example 3") {
        auto nums = std::vector{2,0,2,0,1};
        CHECK(Solution().jump(nums) == 2);
    }

    SECTION("example 4") {
        std::vector<int> nums;
        nums.reserve(25002);
        for (int i = 25000; i >= 1; --i)
            nums.push_back(i);
        nums.push_back(1);
        nums.push_back(0);
        CHECK(Solution().jump(nums) == 2);
    }
}
